A. Field of the Invention
The present invention relates generally to arbitration, and more particularly, to a high performance dequeuing arbitration scheme.
B. Description of Related Art
Routers receive data on a physical media, such as optical fiber, analyze the data to determine its destination, and output the data on a physical media in accordance with the destination. Routers were initially designed using a general purpose processor executing large software programs. As line rates and traffic volume increased, however, general purpose processors could not scale to meet these new demands. For example, as functionality was added to the software, such as accounting and policing functionality, these routers suffered performance degradation. In some instances, the routers failed to handle traffic at the required line rate when the new functionality was enabled.
To meet the new demands, purpose-built routers were designed. Purpose-built routers are designed and built with components optimized for routing. They not only handle higher line rates and higher network traffic volume, but they also add functionality without compromising line rate performance.
A purpose-built router may include a number of input and output ports from which it transmits and receives information packets. A switching fabric may be implemented in the router to carry the packets between ports.
In order to control their high packet throughput, purpose-built routers use buffers to temporarily queue packets waiting to be processed. Arbiters may control the dequeuing of packets from the buffers. Different arbiters may operate on the same buffer to control different aspects of the buffering and dequeuing process. For example, one arbiter may select packets from the queues for transmission while another arbiter may examine the queues for congestion and drop packets from congested queues.
When using multiple arbiters that arbitrate over the same set of queues, it is desirable to implement the arbiters in a manner that is as efficient as possible. Preferably, total bandwidth through the arbiters should be maximized while sharing common resources related to the buffers.